# a consice dp solution

import sys

class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
        for j in range(2, n+1):
            for i in range(j-1, 0, -1):
                minCost = sys.maxsize
                for k in range(i+1, j):
                    cost = max(dp[i][k-1], dp[k+1][j])+k
                    minCost = min(minCost, cost)
                dp[i][j] = (i if i+1==j else minCost)
        return dp[1][n]

print(Solution().getMoneyAmount(100))